package com.LeeCode;

/**
 * 分汤
 */

public class Code808 {
    public static void main(String[] args) {
        int n = 50;
        System.out.println(new Code808().soupServings(n));
    }

    public double soupServings(int n) {
        // 当n很大时，A先耗尽的概率接近1
        // 通过数学分析，当n > 4800时，答案与1的差距小于10^-5
        if (n >= 4800) {
            return 1.0;
        }
        // 离散化：以25ml为单位
        int N = (n + 24) / 25; // 向上取整

        // memo[i][j] 表示A剩余i单位，B剩余j单位时的答案
        double[][] memo = new double[N + 1][N + 1];

        return dp(N, N, memo);
    }

    private double dp(int a, int b, double[][] memo) {
        // 边界条件
        if (a <= 0 && b <= 0) {
            // A和B都耗尽，贡献0.5
            return 0.5;
        }
        if (a <= 0) {
            // 只有A耗尽，贡献1.0
            return 1.0;
        }
        if (b <= 0) {
            // 只有B耗尽，贡献0.0
            return 0.0;
        }

        // 记忆化
        if (memo[a][b] > 0) {
            return memo[a][b];
        }

        // 四种操作，每种概率0.25
        double result = 0.25 * (
                dp(a - 4, b, memo) +     // 操作1: A-4, B-0
                        dp(a - 3, b - 1, memo) + // 操作2: A-3, B-1
                        dp(a - 2, b - 2, memo) + // 操作3: A-2, B-2
                        dp(a - 1, b - 3, memo)   // 操作4: A-1, B-3
        );

        memo[a][b] = result;
        return result;
    }
}
